sortlistmodel: Use GtkSortKeys
authorBenjamin Otte <otte@redhat.com>
Tue, 21 Jul 2020 01:40:28 +0000 (03:40 +0200)
committerBenjamin Otte <otte@redhat.com>
Wed, 22 Jul 2020 12:30:49 +0000 (14:30 +0200)
commit3b24c8a0a4782d1118520005376ed0b5c60d43d3
tree888c8899b91295774cba234ac897999583682478
parente34c7e6796b995070989637c5faef13688508827
sortlistmodel: Use GtkSortKeys

This massively speeds up sorting with expensive sort functions that it's
the most worthwhile optimization of this whole branch.
It's slower for simple sort functions though.

It's also quite a lot slower when the model doesn't support sort keys
(like GtkCustomSorter), but all the other sorters do support keys.

Of course, this depends on the number of items in the model - the number
of comparisons scales O(N * log N) while the overhead for key handling
scales O(N).
So as the log N part grows, generating keys gets more and more
beneficial.

Benchmarks:

       initial sort of a GFileInfo model with display-name keys
                       items     keys
         8,000 items   715ms     50ms
        64,000 items     ---    554ms

       initial sort of a GFileInfo model with complex keys
                       items     keys
        64,000 items   340ms    295ms
       128,000 items   641ms    605ms

       removing half a GFileInfo model with display-name keys
       (no comparisons, just key freeing overhead of a complex sorter)
                       items     keys
       512,000 items    14ms     21ms
     2,048,000 items    40ms     62ms

       removing half a GFileInfo model with complex keys
       (no comparisons, just key freeing overhead of a complex sorter)
                       items     keys
       512,000 items    90ms    237ms
     2,048,000 items   247ms    601ms
gtk/gtksortlistmodel.c